/**
 * 
 */
package com.gragra.clustering;
import java.util.ArrayList;
import java.util.Iterator;
import it.unimi.dsi.fastutil.ints.Int2ObjectMap.Entry;
import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import it.unimi.dsi.fastutil.objects.ObjectIterator;
import com.gragra.data.MixingCorpus;
import com.gragra.data.MixingCorpusBaseImplementation;
import com.gragra.distances.MeanFactory;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.vector.VectorStructure;
/**
 * An implementation of Clustering by dividing based on 2-Means Clustering, in the end the semantic of the assigned
 * clusters is as follows: if the cluster numbers are written in binary, then the 0s and 1s read from left
 * to right indicate which split an entry was assigned at the given level
 * @author Christoph Teichmann
 * 03.05.2013
 */
public class DivisiveKMeansBasedClustering implements ClusteringAlgorithm
{
	/**
	 * the number of levels that will be generated
	 */
	private final int levels;
	/**
	 * the means factory that will be used
	 */
	private final MeanFactory mf;
	/**
	 * the maximum number of iterations used per division
	 */
	private final int maxIterationsPerDivision;
	/**
	 * creates a new instance that will have the given number of hierarchy levels
	 * @param levels
	 * @param mf
	 * @param maxIterationsPerDivision
	 */
	public DivisiveKMeansBasedClustering(int levels, MeanFactory mf,
			int maxIterationsPerDivision)
	{
		super();
		this.levels = levels;
		this.mf = mf;
		this.maxIterationsPerDivision = maxIterationsPerDivision;
	}
	@Override
	public void cluster(MixingCorpus<? extends VectorStructure> corpus, ThreadedUniformAccess tua)
	{
		Int2ObjectOpenHashMap<ArrayList<VectorStructure>> old = new Int2ObjectOpenHashMap<ArrayList<VectorStructure>>();
		Int2ObjectOpenHashMap<ArrayList<VectorStructure>> next = new Int2ObjectOpenHashMap<ArrayList<VectorStructure>>();
		ArrayList<VectorStructure> al = new ArrayList<VectorStructure>();
		for(VectorStructure vs : corpus)
		{al.add(vs);}
		old.put(0, al);
		for(int i=0;i<this.levels;++i)
		{
			next.clear();
			ObjectIterator<Entry<ArrayList<VectorStructure>>> set = old.int2ObjectEntrySet().fastIterator();
			while(set.hasNext())
			{
				Entry<ArrayList<VectorStructure>> ent = set.next();
				if(ent.getValue().size() < 2)
				{
					next.put(ent.getKey()*2, ent.getValue());
					continue;
				}
				int key = ent.getIntKey();
				MixingCorpus<VectorStructure> corp = new MixingCorpusBaseImplementation<VectorStructure>();
				corp.addData(ent.getValue());
				KMeansClusterer kmc = new KMeansClusterer(mf, maxIterationsPerDivision, 2);
				kmc.cluster(corp,tua);
				ArrayList<VectorStructure> one = new ArrayList<VectorStructure>(corp.size()/2);
				ArrayList<VectorStructure> two = new ArrayList<VectorStructure>(corp.size()/2);
				for(int j=0;j<corp.size();++j)
				{
					int name = kmc.getBest(corp.getEntry(j), j);
					if(name < 1)
					{one.add(corp.getEntry(j));}
					else
					{two.add(corp.getEntry(j));}
				}
				next.put(key*2, one);
				next.put(key*2+1, two);
			}
			old.clear();
			old.putAll(next);
		}
		Iterator<Entry<ArrayList<VectorStructure>>> ent = old.int2ObjectEntrySet().fastIterator();
		while(ent.hasNext())
		{
			Entry<ArrayList<VectorStructure>> inst = ent.next();
			int key = inst.getIntKey();
			for(VectorStructure vs : inst.getValue())
			{this.mapping.put(vs, key);}
		}
	}
	/**
	 * the final mapping from VectorStructures to cluster numbers used
	 */
	private final Object2IntMap<VectorStructure> mapping = new Object2IntOpenHashMap<VectorStructure>();
	@Override
	public int getBest(VectorStructure vs, int number)
	{return mapping.getInt(vs);}
}